package sort;

/**
 * @Author: Dang Qi
 * @Date: 2021/4/7  16:49
 * @Description:
 */
public class MergeSort {
    public static int[] mergeSort(int[] a){
        return  mergeSort(a, 0, a.length-1, new int[a.length]);
    }
    public static int[] mergeSort(int[] a, int i, int j, int[] tmp){
        if(i>=j) return a;
        int mid = (i+j)/2;
        mergeSort(a, i, mid, tmp);
        mergeSort(a,mid+1, j, tmp);
        merge(a, i, j, tmp);
        return a;
    }
    public static void merge(int[] a, int lo, int hi, int[] tmp){
        for(int k = lo; k <= hi ; k++){
            tmp[k] = a[k];
        }
        int index = lo, mid = (lo+hi)/2;
        int i = lo, j = mid + 1;
        while(i <= mid && j <=hi){
            while(i <= mid && tmp[i] <= tmp[j])  a[index++] = tmp[i++];

            while(i <= mid && j<=hi && tmp[i] >= tmp[j])  a[index++] = tmp[j++];
        }
        while(i <= mid)  a[index++] = tmp[i++];
        while(j <= hi)  a[index++] = tmp[j++];
    }
}
